/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 找到最大值 超时了 最坏情况O(n^2)超时
var removeNodes1 = function (head) {
  const getMaxValue = function (p) {
    let temp_max = p
    while (p) {
      if (p.val > temp_max.val) temp_max = p
      p = p.next
    }
    return temp_max
  }
  let p = head
  current = getMaxValue(p)
  head = current
  while (current.next) {
    current.next = getMaxValue(current.next)
    current = current.next
  }
  current.next = null
  return head
}
var removeNodes2 = function (head) {
  const getMaxValue = function (p) {
    let temp_max = p
    while (p) {
      if (p.val > temp_max.val) temp_max = p
      p = p.next
    }
    return temp_max
  }
  let p = head
  current = getMaxValue(p)
  head = current
  while (current.next) {
    current.next = getMaxValue(current.next)
    current = current.next
  }
  current.next = null
  return head
}
// 记录位置信息整个排序
var removeNodes3 = function (head) {
  let arr = []
  let nodeArr = []
  let p = head
  let index = 0
  while (p) {
    let temp = p
    arr.push({
      val: p.val,
      index: index++
    })
    nodeArr.push(p)
    p = p.next
    temp.next = null
  }
  arr.sort((a, b) => b.val - a.val)
  nodeArr.sort((a, b) => b.val - a.val)
  head = nodeArr[0]
  p = nodeArr[0]
  let currentInx = arr[0].index
  for (let i = 1; i < arr.length; i++) {
    if (arr[i].index > currentInx) {
      p.next = nodeArr[i]
      p = p.next
      currentInx = arr[i].index
    }
  }
  return head
}
// 单调栈
var removeNodes4 = function (head) {
  if (head == null) return head
  const stack = []
  let top = -1
  let p = head
  while (p) {
    if (top == -1) {
      stack[++top] = p
    } else {
      while (stack[top].val < p.val && top > -1) {
        top--
      }
      stack[++top] = p
    }
    p = p.next
  }
  head = stack[0]
  cur = head
  for (let i = 1; i <= top; i++) {
    cur.next = stack[i]
    cur = cur.next
  }
  return head
} 